1849C - Binary String Copying - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int P=998244353;
int n,m,T,cnt,ans;
string a;
int sum1[N],sum2[N],pre[N],nx[N];
set<pair<int,int>> s;
void solve(){
    cin>>n>>m;
    cin>>a;
    s.clear();
    a=" "+a;
    ans=0;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        if(a[i]=='0') pre[i]=i;
    }
    nx[n+1]=n+1;
    for(int i=n;i>=1;i--){
        nx[i]=nx[i+1];
        if(a[i]=='1') nx[i]=i;
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        l=nx[l],r=pre[r];
        if(l>=r) ans=1;
        else {
            s.insert(make_pair(l,r));
        }
    }
    cout<<ans+s.size()<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    //T=1;
    while(T--){
        solve();
    }
    return 0;
}